/**
 * 语法分析器
 *
 * 当前特性：
 * 1.简化版的函数声明
 * 2.简化版的函数调用
 * 3.简化版的表达式
 *
 * 当前语法规则：
 * prog = statementList? EOF
 * statementList = (variableDecl | functionDecl | expressionStatement)+
 * variableDecl : 'let' Identifier typeAnnotation？ ('=' singleExpression) ' '
 * typeAnnotation : ':' typeName
 * functionDecl: "function" Identifier "(" ")"  functionBody
 * functionBody : '{' statementList? '}'
 * statement: functionDecl | expressionStatement
 * expressionStatement: expression ' '
 * expression: primary (binOP primary)*
 * primary: StringLiteral | DecimalLiteral | IntegerLiteral | functionCall | '(' expression ')'
 * binOP: '+' | '-' | '*' | '/' | '=' | '+=' | '-=' | '*=' | '/=' | '==' | '!=' | '<=' | '>=' | '<'
 *      | '>' | '&&'| '||'|...
 * functionCall : Identifier '(' parameterList? ')'
 * parameterList : expression (',' expression)*
 */

package mynl

import (
	"fmt"
)

////////////////////////////////////////////////////////////////////////////////
//Parser

/**
 * 语法解析器。
 * 通常用parseProg()作为入口，解析整个程序。也可以用下级的某个节点作为入口，只解析一部分语法。
 */
type Parser struct {
	scanner Scanner

	/**
	 * 二元运算符的优先级。
	 */
	OpPrec map[string]int
}

func NewParser(scanner Scanner) *Parser {
	var OpPrec = make(map[string]int)
	OpPrec["="] = 2
	OpPrec["+="] = 2
	OpPrec["-="] = 2
	OpPrec["*="] = 2
	OpPrec["-="] = 2
	OpPrec["%="] = 2
	OpPrec["&="] = 2
	OpPrec["|="] = 2
	OpPrec["^="] = 2
	OpPrec["~="] = 2
	OpPrec["<<="] = 2
	OpPrec[">>="] = 2
	OpPrec[">>>="] = 2
	OpPrec["||"] = 4
	OpPrec["&&"] = 5
	OpPrec["|"] = 6
	OpPrec["^"] = 7
	OpPrec["&"] = 8
	OpPrec["=="] = 9
	OpPrec["==="] = 9
	OpPrec["!="] = 9
	OpPrec["!=="] = 9
	OpPrec[">"] = 10
	OpPrec[">="] = 10
	OpPrec["<"] = 10
	OpPrec["<="] = 10
	OpPrec["<<"] = 11
	OpPrec[">>"] = 11
	OpPrec[">>>"] = 11
	OpPrec["+"] = 12
	OpPrec["-"] = 12
	OpPrec["*"] = 13
	OpPrec["/"] = 13
	OpPrec["%"] = 16

	return &Parser{
		OpPrec:  OpPrec,
		scanner: scanner,
	}
}

/**
 * 解析Prog
 * 语法规则：
 * prog = (functionDecl | functionCall)*
 */
func (selfx *Parser) ParseProg() *Prog {
	return NewProg(selfx.parseStatementList())
}

func (selfx *Parser) parseStatementList() []IStatement {
	var stmts []IStatement
	var t = selfx.scanner.Peek()
	//statementList的Follow集合里有EOF和'}'这两个元素，分别用于prog和functionBody等场景。
	for {
		if t.Kind == TokenKind_EOF || t.Text == "}" {
			break
		}

		var stmt = selfx.parseStatement()
		if stmt != nil {
			stmts = append(stmts, stmt)
		} else {
			fmt.Println("Error parsing a Statement in Programm.")
		}
		t = selfx.scanner.Peek()
	}
	return stmts
}

/**
 * 解析语句。
 * 知识点：在这里，遇到了函数调用、变量声明和变量赋值，都可能是以Identifier开头的情况，所以预读一个Token是不够的，
 * 所以这里预读了两个Token。
 */
func (selfx *Parser) parseStatement() IStatement {
	var t = selfx.scanner.Peek()
	if t.Kind == TokenKind_Keyword && t.Text == "function" {
		return selfx.parseFunctionDecl()
	} else if t.Text == "let" {
		return selfx.parseVariableDecl()
	} else if t.Kind == TokenKind_Identifier ||
		t.Kind == TokenKind_DecimalLiteral ||
		t.Kind == TokenKind_IntegerLiteral ||
		t.Kind == TokenKind_StringLiteral ||
		t.Text == "(" {
		return selfx.parseExpressionStatement()
	} else {
		fmt.Println("Can not recognize a expression starting with: " + selfx.scanner.Peek().Text)
		return nil
	}
}

/**
 * 解析变量声明
 * 语法规则：
 * variableDecl   'let'? Identifier typeAnnotation？ ('=' singleExpression) ' '
 */
func (selfx *Parser) parseVariableDecl() *VariableDecl {
	//跳过'let'
	selfx.scanner.Next()

	var t = selfx.scanner.Next()
	if t.Kind == TokenKind_Identifier {
		var varName string = t.Text

		var varType string = "any"
		var init *IExpression = nil

		var t1 = selfx.scanner.Peek()
		//类型标注
		if t1.Text == ":" {
			selfx.scanner.Next()
			t1 = selfx.scanner.Peek()
			if t1.Kind == TokenKind_Identifier {
				selfx.scanner.Next()
				varType = t1.Text
				t1 = selfx.scanner.Peek()
			} else {
				fmt.Println("Error parsing type annotation in VariableDecl")
				return nil
			}
		}

		//初始化部分
		if t1.Text == "=" {
			selfx.scanner.Next()
			init = selfx.parseExpression()
		}

		//分号
		t1 = selfx.scanner.Peek()
		if t1.Text == ";" {
			selfx.scanner.Next()
			return NewVariableDecl(varName, varType, init)
		} else {
			fmt.Println("Expecting   at the end of varaible declaration, while we meet " + t1.Text)
			return nil
		}
	} else {
		fmt.Println("Expecting variable name in VariableDecl, while we meet " + t.Text)
		return nil
	}
}

/**
 * 解析函数声明
 * 语法规则：
 * functionDecl: "function" Identifier "(" ")"  functionBody
 * 返回值：
 * nil-意味着解析过程出错。
 */
func (selfx *Parser) parseFunctionDecl() *FunctionDecl {
	//跳过关键字'function'
	selfx.scanner.Next()

	var t = selfx.scanner.Next()
	if t.Kind == TokenKind_Identifier {
		//读取"("和")"
		var t1 = selfx.scanner.Next()
		if t1.Text == "(" {
			var t2 = selfx.scanner.Next()
			if t2.Text == ")" {
				//尝试读取FunctionBody
				var functionBody = selfx.parseFunctionBody()
				if functionBody != nil {
					fmt.Println("parseFunctionBody successed!")
					//如果解析成功，从这里返回
					return NewFunctionDecl(t.Text, *functionBody)
				} else {
					fmt.Println("Error parsing FunctionBody in FunctionDecl")
					return nil
				}
			} else {
				//括号不匹配
				fmt.Println("Expecting ')' in FunctionDecl, while we got a " + t.Text)
				return nil
			}
		} else {
			//函数声明格式不正确
			fmt.Println("Expecting '(' in FunctionDecl, while we got a " + t.Text)
			return nil
		}
	} else {
		fmt.Println("Expecting a function name, while we got a " + t.Text)
		return nil
	}

	//如果解析不成功，返回null。
	//return nil
}

/**
 * 解析函数体
 * 语法规则：
 * functionBody : '{' functionCall* '}'
 */
func (selfx *Parser) parseFunctionBody() *Block {
	var t *Token = selfx.scanner.Peek()
	if t.Text == "{" {
		selfx.scanner.Next()
		var stmts = selfx.parseStatementList()
		t = selfx.scanner.Next()
		if t.Text == "}" {
			//Block读取结束
			return NewBlock(stmts)
		} else {
			fmt.Println("Expecting '}' in FunctionBody, while we got a " + t.Text)
			return nil
		}
	} else {
		//Block格式错误
		fmt.Println("Expecting '{' in FunctionBody, while we got a " + t.Text)
		return nil
	}
}

/**
 * 解析表达式语句
 */
func (selfx *Parser) parseExpressionStatement() *ExpressionStatement {
	var exp = selfx.parseExpression()
	if exp != nil {
		var t = selfx.scanner.Peek()
		if t.Text == ";" {
			selfx.scanner.Next()
			return NewExpressionStatement(*exp)
		} else {
			fmt.Println("Expecting a semicolon at the end of an expresson statement, while we got a " + t.Text)
		}
	} else {
		fmt.Println("Error parsing ExpressionStatement")
	}

	//如果解析不成功，返回null。
	return nil
}

/**
 * 解析表达式
 */
func (selfx *Parser) parseExpression() *IExpression {
	return selfx.parseBinary(0)
}

/**
 * 获取运算符优先级
 */
func (selfx *Parser) getPrec(op string) int {
	ret, ok := selfx.OpPrec[op]
	if !ok {
		return -1
	} else {
		return ret
	}
}

/**
 * 采用运算符优先级算法，解析二元表达式。
 * 这是一个递归算法。一开始，提供的参数是最低优先级，
 *
 * @param prec 当前运算符的优先级
 */
func (selfx *Parser) parseBinary(prec int) *IExpression {
	// 首先解析一个基础表达式，作为左子节点
	// fmt.Println("parseBinary   " + prec)
	var exp1 = selfx.parsePrimary()
	if exp1 != nil {
		//预读运算符
		var t = selfx.scanner.Peek()
		//获取运算符的优先级
		var tprec = selfx.getPrec(t.Text)

		//下面这个循环的意思是：只要右边出现的新运算符的优先级更高，
		//那么就把右边出现的作为右子节点。
		/**
		 * 对于2+3*5
		 * 第一次循环，遇到+号，优先级大于零，所以做一次递归的binary
		 * 在递归的binary中，遇到乘号，优先级大于+号，所以形成3*5返回，又变成上一级的右子节点。
		 *
		 * 反过来，如果是3*5+2
		 * 第一次循环还是一样。
		 * 在递归中，新的运算符的优先级要小，所以只返回一个5，跟前一个节点形成3*5.
		 */

		//只要优先级比当前要求的优先级大
		for {
			if t.Kind != TokenKind_Operator || tprec <= prec {
				break
			}
			selfx.scanner.Next() //跳过运算符

			//针对优先级更高的运算符，获取一棵AST子树
			var exp2 = selfx.parseBinary(tprec)
			if exp2 != nil {
				//创建一棵新的AST，把刚刚获取的AST子树作为右子树
				var exp *BinaryOP = NewBinaryOP(t.Text, exp1, *exp2)
				exp1 = exp
				t = selfx.scanner.Peek()
				tprec = selfx.getPrec(t.Text)
			} else {
				fmt.Println("Can not recognize a expression starting with: ", t.Text)
			}
		}
		return &exp1
	} else {
		fmt.Println("Can not recognize a expression starting with: ", selfx.scanner.Peek().Text)
		return nil
	}
}

/**
 * 解析基础表达式。
 */
func (selfx *Parser) parsePrimary() IExpression {
	var t = selfx.scanner.Peek()
	fmt.Println("parsePrimary  " + t.Text)

	//知识点：以Identifier开头，可能是函数调用，也可能是一个变量，所以要再多向后看一个Token，
	//这相当于在局部使用了LL(2)算法。
	if t.Kind == TokenKind_Identifier {
		if selfx.scanner.Peek2().Text == "(" {
			return selfx.parseFunctionCall()
		} else {
			selfx.scanner.Next()
			return NewVariable(t.Text)
		}
	} else if t.Kind == TokenKind_IntegerLiteral {
		selfx.scanner.Next()
		return NewIntegerLiteral(t.Text)
	} else if t.Kind == TokenKind_DecimalLiteral {
		selfx.scanner.Next()
		return NewDecimalLiteral(t.Text)
	} else if t.Kind == TokenKind_StringLiteral {
		selfx.scanner.Next()
		return NewStringLiteral(t.Text)
	} else if t.Text == "(" {
		selfx.scanner.Next()
		var exp = selfx.parseExpression()
		var t1 = selfx.scanner.Peek()
		if t1.Text == ")" {
			selfx.scanner.Next()
			return *exp
		} else {
			fmt.Println("Expecting a ')' at the end of a primary expresson, while we got a " + t.Text)
			return nil
		}
	} else {
		fmt.Println("Can not recognize a primary expression starting with: " + t.Text)
		return nil
	}
}

/**
 * 解析函数调用
 * 语法规则：
 * functionCall : Identifier '(' parameterList? ')'
 * parameterList : StringLiteral (',' StringLiteral)*
 */
func (selfx *Parser) parseFunctionCall() *FunctionCall {
	var params []IExpression
	var t *Token = selfx.scanner.Next()
	if t.Kind == TokenKind_Identifier {
		var t1 *Token = selfx.scanner.Next()
		if t1.Text == "(" {
			//循环，读出所有参数
			t1 = selfx.scanner.Peek()
			for {
				if t1.Text == ")" {
					break
				}
				//参数读取
				var exp = selfx.parseExpression()
				if exp != nil {
					params = append(params, *exp)
				} else {
					fmt.Println("Error parsing parameter in function call")
					return nil
				}

				t1 = selfx.scanner.Peek()
				//参数部分未结束，分析其他参数
				if t1.Text != ")" {
					if t1.Text == "," {
						//其他参数
						t1 = selfx.scanner.Next()
					} else {
						//格式错误
						fmt.Println("Expecting a comma at the end of a function call, while we got a " + t1.Text)
						return nil
					}
				}
			}

			//参数获取完毕
			//消化掉')'
			selfx.scanner.Next()

			return NewFunctionCall(t.Text, params)
		}
	}

	//如果解析不成功，返回null。
	return nil
}
